# @Time      :2024/3/8 11:38
# @Author    :Dun_Hz
# @FileName  :migong_zhan.py
# @Software  :PyCharm
mi_gong = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0, 1, 0, 1, 1, 1],
    [1, 0, 0, 1, 0, 0, 0, 0, 1, 1],
    [1, 0, 0, 0, 0, 1, 1, 1, 1, 1],
    [1, 1, 0, 1, 0, 1, 0, 1, 1, 1],
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 1, 1, 0, 1, 0, 1, 0, 1, 1],
    [1, 1, 1, 0, 0, 0, 1, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
dirs = [
    lambda x, y: (x + 1, y),
    lambda x, y: (x - 1, y),
    lambda x, y: (x, y + 1),
    lambda x, y: (x, y - 1)
]


def mi_gong_path(x1, y1, x2, y2):
    stack = []
    stack.append((x1, y1))
    while len(stack) > 0:
        CurNode = stack[-1]     #表示当前位置，栈是先进后出，存入当前位置坐标
        if CurNode[0]==x2 and CurNode[1]==y2:
            print('走到终点了')
            for i in stack:
                print(i)
            return True
        for dir in dirs:
            NextNode = dir(CurNode[0], CurNode[1])      #下一步的位置坐标（x, y）
            # 如果能走的话：
            if mi_gong[NextNode[0]][NextNode[1]] == 0:
                stack.append(NextNode)
                mi_gong[NextNode[0]][NextNode[1]] = 2   #走过的点标记为2
                break   #不考虑其他点
        else:
            # mi_gong[CurNode[0]][CurNode[1]] = 2
            stack.pop()

    else:
        print('不可能过去')
        return False

mi_gong_path(1,1,7,8)
for i in mi_gong:
    print(i)